1. The Field of the Invention
This invention relates to cryptography and, more particularly, to novel systems and methods for increasing the speed of cryptographic key computations by computers.
2. The Background Art
The science of cryptography has existed since ancient times. In recent years, cryptography has been used in special purpose software programs for a variety of purposes, such as hiding underlying contents, limiting access, inhibiting reverse engineering, authenticating sources, limiting unauthorized use, and the like.
Cryptographic Processes
Modem cryptography protects data transmitted over a network or stored in computer systems. Two principal objectives of cryptography include (1) secrecy, e.g., to prevent the unauthorized disclosure of data, and (2) integrity (or authenticity), e.g., to prevent the unauthorized modification of data. Encryption is the process of disguising plaintext data in such a way as to hide its contents, and the encrypted result is known as ciphertext. The process of turning ciphertext back into plaintext is called decryption.
A cryptographic algorithm, also known as a cipher, is a computational function used to perform encryption and/or decryption. Both encryption and decryption are controlled by one or more cryptographic keys. In modem cryptography, all of the security of cryptographic algorithms is based on the key(s) and does not require keeping the details of the cryptographic algorithms secret.
There are two general types of key-based cryptographic algorithms: symmetric and public-key. In symmetric algorithms, the encryption key can be calculated from the decryption key and vice versa. Typically, these keys are the same. As such, a sender and a receiver agree on the keys (a shared secret) before they can protect their communications using encryption. The security of the algorithms rests in the key, and divulging the key allows anyone to encrypt and decrypt data or messages with it.
In public-key algorithms (also called asymmetric algorithms), the keys used for encryption and decryption differ in such a way that at least one key is computationally infeasible to determine from the other. To ensure secrecy of data or communications, only the decryption key need be kept private, and the encryption key can thus be made public without danger of encrypted data being decipherable by anyone other than the holder of the private decryption key.
Conversely, to ensure integrity of data or communications, only the encryption key need be kept private, and a holder of a publicly-exposed decryption key can be assured that any ciphertext that decrypts into meaningful plaintext using this key could only have been encrypted by the holder of the corresponding private key, thus precluding any tampering or corruption of the ciphertext after its encryption.
A private key and a public key may be thought of as functionally reciprocal. Thus, whatever a possessor of one key of a key pair can do, a possessor of the other key of the key pair can undo. Accordingly, secret information may be communicated without an exchange of keys.
An asymmetric algorithm assumes that public keys are well publicized in an integrity-secure manner. A sender can then know that the public key of the receiver is valid and not tampered with. One way to ensure integrity of data packets is to run data through a cryptographic algorithm. A cryptographic hash algorithm may encrypt and compress selected data. Various cryptographic hash algorithms are known, such as the Secure Hash Algorithm (SHA) and Message Digest 5 (MD5).
A certificate is a data structure associated with assurance of integrity and/or privacy of encrypted data. A certificate binds the identity of a holder to a public key of that holder, and may be signed by a certification authority (CA). In a public key infrastructure (PKI), a hierarchy of certification authorities may be provided, each level vouching for the authenticity of the public keys of subordinate levels.
A certificate may contain data regarding the identity of the entity being certified, the key held (typically a public key), the identity (typically self-authenticating) of the certifying authority issuing the certificate to the holder, and a digital signature protecting the integrity of the certificate itself. A digital signature may typically be based on the private key of the certifying authority issuing the certificate to the holder. Thus, any entity to whom the certificate is asserted may verify the signature corresponding to the private key of the certifying authority.
In general, a signature of a certifying authority is a digital signature. The digital signature associated with a certificate enables a holder of the certificate, and one to whom the certificate is asserted as authority of the holder, to use the signature of the certifying authority to verify that nothing in the certificate has been modified. This verification is accomplished using the certificate authority""s public key, thus providing a means for verifying the integrity and authenticity of the certificate and of the public key in the certificate.
Various cryptographic techniques rely on elliptic curves. Code and documentation for the use of elliptic curves in cryptography are available. For example, standard references, including certain algebra texts discussing Galois Fields, sometimes called xe2x80x9cfinite fields,xe2x80x9d are available in the art.
One reason for interest in acceleration of elliptic curve processing is the increasing size of cryptographic keys. Mathematical calculations often increase geometrically with the size of the keys. Accordingly, if the speed of elliptic curve processing can be increased, less processing time is required for more secure, longer cryptographic keys. Thus, what is needed is methods and apparatus for accelerating computations associated with creating, weaving, and processing of cryptographic keys.
In view of the foregoing, it is a primary object of the present invention to provide an apparatus and method comprising an elliptic curve, point-doubling system.
Consistent with the foregoing object, and in accordance with the invention as embodied and broadly described herein, an apparatus and method are disclosed in certain embodiments of the present invention as including a method and apparatus for operating a cryptographic engine supporting a key generation module. The key generation module creates key pairs for encryption on substantive content to be shared between two users over a secured or unsecured communication link.
A principal feature provided by an apparatus and method in accordance with the invention includes a point-doubling module as part of an elliptic curve module within a key generation module for creating and processing keys. Hash functions may be used to further process ephemeral secrets or ephemeral keys that may be used for transactions, sessions, or other comparatively short time increments of communication.
The keys generated by the key generation module may be configured to be processable by an encryption system for divulging independently to two independent parties a secret to be shared by the two independent parties. In various embodiments, a single-inversion, point-doubling algorithm is provided to reduce the operation count of a cryptographic process.
In one aspect of the invention, the point doubling module may include a register for storing an ordered pair of variables selected to be operated on for executing single-inversion point-doubling. The ordered pairs may represents a set of coordinates corresponding to a point on an elliptic curve.
In another aspect, the point-doubling module may include a plurality of ordered tuples reflecting points on an abelian variety. The ordered tuples may include ordered pairs. An ordered pair may include a first element and a second element, wherein the value of the second element may include the result of an exclusive OR operation on the first element and a previous value of the second element. In various embodiments, the abelian variety may include a hyperelliptic curve.
In yet another aspect, the ordered pair may include first and second elements, wherein the second element is a ratio reflecting coordinates of a first point on an elliptic curve. In various embodiments, the ratio may be a quotient of a Y coordinate divided by an X coordinate on an elliptic curve. Moreover, the first point may be computed by a computation method selected from the group consisting of a multiplication, a division, and a multiplication and a division. The computation method may operate on first and second points on an elliptic curve.
In still another aspect, the apparatus may include an application module programmed to execute a function selected from encryption of a substantive content, decryption, maintaining privacy of private information, authentication of received information, validation of exchanged information, a digital signature, hashing, key distribution, random number generation, determining the order of a curve, determining the order of a point, determining the discrete logarithm of a point, and breaking a cryptographic system.
In another aspect of the invention, the elliptic curve module may include a point multiplication algorithm using two distinct representations of a selected points on an elliptic curve. In various embodiments, the two distinct representations include a first representation and a second representation, wherein the point multiplication algorithm selectively alternates between processing the first representation and the second representation.
The above objects may be met by one or more embodiments of an apparatus and method in accordance with the invention. Likewise, one or more embodiments of an apparatus and method in accordance with the invention may provide the desirable features as described.